(1) Field of the Invention
The invention relates to the scheduling of traffic in a switch/router. More particularly, the invention relates to supporting increases in switch/router port speeds, providing improved performance in servicing traffic flows of multiple priorities, and providing frame-aware scheduling.
(2) Description of the Related Art
Communication networks typically use devices for directing the flow of data through them. Such devices are often characterized as switches and routers, which may be referred to collectively as switches/routers. A switch/router receiving data at a plurality of inputs often needs to schedule the processing of such data so as to produce one or more output streams that conform to particular criteria. However, switches/routers often exhibit deficiencies that prevent them from maintaining conformance with some of the particular criteria that may be desired.
FIG. 1 is a block diagram illustrating a prior art scheduling technique. The technique includes input queues 101 and 102 coupled to scheduler 103 via connections 113 and 114, respectively. Additional input queues maybe coupled to scheduler 103 via connection 115. Scheduler 103 provides an output 116 to input queue 104. Input queue 104 is coupled to scheduler 105 via connection 117. Additional input queues may be coupled to scheduler via connection 118 and/or 119. Scheduler 105 provides an output 120 to input queue 106. Input queue 106 is coupled to scheduler 107 via connection 121. Input queue 108 is coupled to scheduler 109 via connection 124. Additional input queues may be coupled to scheduler 109 via connection 125 and/or 126. Scheduler 109 provides output 127 to input queue 110. Input queue 110 is coupled to scheduler 111 via connection 128. Additional input queue may be coupled to scheduler 111 via connection 129 and/or 130. Scheduler 111 provides output 131 to input queue 112. Input queue 112 is coupled to scheduler 107 via connection 132. Additional input queues may be coupled to scheduler 107 via connection 122. Scheduler 107 provides output 123.
As an example, cell 133 is provided to input queue 101. The structure of this system may be considered hierarchical, with cells, such as cell 133 being provided to input queues, such as 101, 102, and 108. At the next level of the hierarchy, referred to as select queue 134, a first level of scheduler, such as scheduler 103 and 109, process the output of the first level of input queues, which includes input queues 101, 102, and 108. From the level of select queue 134, the hierarchy continues to a level of select class 135, which includes input queues 104 and 110, as well as schedulers 105 and 111. From select class 135, the system proceeds to a level for select port 136. The level select port 136 includes input queues 106 and 112, as well as scheduler 107.
The prior art technique illustrated in FIG. 1 comprises a plurality (K) of input queues coupled at their outputs to a hierarchical arrangement of schedulers, the schedulers being arranged in levels with inter-level queues between the schedulers and each inter-level queue coupled to a corresponding scheduler output. Each level of schedulers corresponds to a particular scheduling function, for example, selecting a port, selecting a traffic class, and selecting an input queue.
For example, in operation input queue A is serviced by queue-selection level scheduler 103. Scheduler 103 outputs cells to inter-level queue 104, which is serviced by class-selection level scheduler 105. Scheduler 105 outputs cells to inter-level queue 106. Inter-level queue 106 is serviced by port-selection scheduler 107, which outputs cells to an output port, or switching fabric, of the switch/router.
Frame-aware scheduling is performed to ensure that all cells of a frame are transmitted from a port in a continuous stream, without interruption by other cells. This type of scheduling is used for packet over SONET (POS) transmission, for example. To provide frame-aware scheduling, once scheduling on a frame starts the scheduler must continue to select cells from the frame until an end of frame indication is reached. A start of frame (SOF) indication and an end of frame (EOF) indication are used to delimit the frame. The cells of a frame are eligible for transmission when the entire frame has been received as indicated by the EOF. The cells of a frame can be treated for purposes of scheduling to have arrived when the EOF is received.
However, a problem exists with the aforementioned prior art technique in that the arrival order of data can take precedence over priority assigned to individual units of data. This is because once data has been moved to an inter-level queue by the corresponding scheduler, it is not possible for any data to be placed in the inter-level queue ahead of that data. This means that a newly arrived frame having a priority higher than that of the frame(s) in the inter-level queue must wait until the entire queue contents ahead of it are serviced before it can be serviced. Although this problem exists in scheduler arrangements of this form that are not frame-aware, the problem is exacerbated with frame-aware scheduling because frames can contain a very large number of cells.
Another aspect of the scheduler arrangement illustrated in FIG. 1 involves the timing of the propagation of cells through the scheduler. A cell arrives at input queue 101 resulting in input queue 101 being updated at time t0. At time t0+ (i.e., t0 plus some small delta that is less than a cell time) scheduler 103 selects input queue 101 and forwards the cell to inter-level queue 104. Note that, in practice, cell pointers are manipulated from queue to queue instead of actual cells. Inter-level queue 104 is updated at the next cell time slot, time t1. At time t1+, scheduler 105 selects inter-level queue 104 and forwards the cell to inter-level queue 106. Inter-level queue 106 is updated at the next cell time slot, time t2. At time t2+, scheduler 107 selects inter-level queue 106 and forwards the cell to the switching fabric, or output port.
In general, with this type of arrangement, the time taken for a cell to effectively propagate through the scheduler increases linearly with the number of levels in the scheduling hierarchy, i.e., propagation time=N×cell time (or N×cell period). In the example, since there are three levels of hierarchy it takes three cell time slots for cells to propagate through the arrangement of schedulers.
There are two main problems with the aforementioned prior art technique. Firstly, adding more levels to the scheduling hierarchy, e.g., to support more segregation of traffic into sub-classes, aggregates, multiple services etc, linearly increases the time taken for cells to propagate through the scheduling arrangements. This is undesirable because it delays the response of the switch/router to conditions at its inputs, which adversely affects its performance. Secondly, arrival order of cells can take precedence over priority assigned to cells. This problem occurs because scheduling selections made at each level are made only on the basis of cells that have been forwarded from the previous level to the inter-level queues between the levels. For example, referring to FIG. 1, scheduler 107 cannot respond to a high priority cell arriving at input queue A until the cell has been propagated to the inter-level queue 106. This condition is undesirable because it adversely affects the intended control of traffic on an assigned priority basis. Thus, a solution is needed that avoids the disadvantages of the prior art technique described above.
The use of the same reference symbols in different drawings indicates similar or identical items.